BZOJ3226【SDOI2008】校门外的区间 <线段树>

Problem

【SDOI2008】校门外的区间

Description

受校门外的树这道经典问题的启发，君根据基本的离散数学的知识，抽象出种运算维护集合(初始为空)并最终输出。现在，请你完成这道校门外的树之难度增强版——校门外的区间。
种运算如下：

编号	表示格式	数学表示

基本集合运算如下：

运算	结果

Input

输入共行。
每行的格式为，用一个空格隔开，表示运算的种类，为一个区间(区间用表示)。

Output

共一行，即集合，每个区间后面带一个空格。若为空则输出。

Sample Input

U [1,5]
D [3,3]
S [2,4]
C (1,5)
I (2,3]

Sample Output

(2,3)

HINT

对于的数据，，

标签：线段树

Solution

假设只有闭区间，对于每个数，标记其为还是。
四种运算对应如下（为区间修改，为区间取反）：

再考虑加入开区间，开区间看作对应的闭区间。即将看作。
为了存的小数，我们将所有区间均乘，即变为。
又考虑到有的区间，因而对于所有区间两端点再加，即变为。
最后用线段树维护即可。
对于输出，扫一遍，找出每个数是还是，然后合并区间，双指针跑。
本题细节较多，写的时候得小心。

Code

#include <iostream>
#include <cstdio>
#define n (65536*2+1)
using namespace std;
struct node {int val, tag, rev;} tr[n*4+500];
void build(int v, int s, int t) {
    tr[v].tag = -1;	if (s == t)	return;	int mid = s+t>>1;
    build(v<<1, s, mid), build(v<<1|1, mid+1, t);
}
void downtag(int v, int s, int t) {
    if (s == t) {if (~tr[v].tag)	tr[v].val = tr[v].tag;	tr[v].val ^= tr[v].rev, tr[v].tag = -1, tr[v].rev = 0;	return;}
    if (~tr[v].tag)	tr[v<<1].tag = tr[v<<1|1].tag = tr[v].tag, tr[v<<1].rev = tr[v<<1|1].rev = 0;
    tr[v<<1].rev ^= tr[v].rev, tr[v<<1|1].rev ^= tr[v].rev;	tr[v].tag = -1, tr[v].rev = 0;
}
int query(int v, int s, int t, int p) {
    downtag(v, s, t);	if (s == t)	return tr[v].val;	int mid = s+t>>1;
    return p <= mid ? query(v<<1, s, mid, p) : query(v<<1|1, mid+1, t, p);
}
void modify(int v, int s, int t, int l, int r, int x) {
    if (s > t)	return;	downtag(v, s, t);
    if (s >= l && t <= r) {tr[v].tag = x;	return;}
    int mid = s+t>>1;
    if (l <= mid)	modify(v<<1, s, mid, l, r, x);
    if (r >= mid+1)	modify(v<<1|1, mid+1, t, l, r, x);
}
void reverse(int v, int s, int t, int l, int r) {
    if (s > t)	return;	downtag(v, s, t);
    if (s >= l && t <= r) {tr[v].rev ^= 1;	return;}
    int mid = s+t>>1;
    if (l <= mid)	reverse(v<<1, s, mid, l, r);
    if (r >= mid+1)	reverse(v<<1|1, mid+1, t, l, r);
}
int main() {
    char opt, lbr, rbr;	int l, r;	build(1, 1, n);
    while (~scanf("%c %c%d,%d%c\n", &opt, &lbr, &l, &r, &rbr)) {
        l <<= 1, r <<= 1, l = l+(lbr == '(')+2, r = r-(rbr == ')')+2;
        if (opt == 'U')	modify(1, 1, n, l, r, 1);
        if (opt == 'I')	modify(1, 1, n, 1, l-1, 0), modify(1, 1, n, r+1, n, 0);
        if (opt == 'D')	modify(1, 1, n, l, r, 0);
        if (opt == 'C')	modify(1, 1, n, 1, l-1, 0), modify(1, 1, n, r+1, n, 0), reverse(1, 1, n, l, r);
        if (opt == 'S')	reverse(1, 1, n, l, r);
    }
    int st = -1, en = -1;	bool flag = false;
    for (int i = 1; i <= n; i++) {
        if (query(1, 1, n, i)) {
            if (st == -1)	st = i;
            en = i;
        } else {
            if (~st) {
                if (flag)	printf(" ");
                else	flag = true;
                printf("%c", (st%2 == 1) ? '(' : '[');
                printf("%d,%d", st/2-1, (en+1)/2-1);
                printf("%c", (en%2 == 1) ? ')' : ']');
            }
            st = en = -1;
        }
    }
    if (!flag)	printf("empty set");
    return 0;
}